/**
 * 数据结构作业 - 二叉树实现
 * 实现一个简单的二叉搜索树
 */
public class BinaryTree<T extends Comparable<T>> {
    private class Node {
        T data;
        Node left;
        Node right;
        
        Node(T data) {
            this.data = data;
            left = null;
            right = null;
        }
    }
    
    private Node root;
    
    public BinaryTree() {
        root = null;
    }
    
    // 插入节点
    public void insert(T data) {
        root = insertRec(root, data);
    }
    
    private Node insertRec(Node root, T data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        
        if (data.compareTo(root.data) < 0)
            root.left = insertRec(root.left, data);
        else if (data.compareTo(root.data) > 0)
            root.right = insertRec(root.right, data);
            
        return root;
    }
    
    // 中序遍历
    public void inorderTraversal() {
        System.out.println("中序遍历结果：");
        inorderRec(root);
        System.out.println();
    }
    
    private void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }
    
    // 查找节点
    public boolean search(T data) {
        return searchRec(root, data);
    }
    
    private boolean searchRec(Node root, T data) {
        if (root == null || root.data.equals(data))
            return root != null;
            
        if (data.compareTo(root.data) < 0)
            return searchRec(root.left, data);
            
        return searchRec(root.right, data);
    }
    
    // 获取树的高度
    public int height() {
        return heightRec(root);
    }
    
    private int heightRec(Node root) {
        if (root == null)
            return 0;
        else {
            int leftHeight = heightRec(root.left);
            int rightHeight = heightRec(root.right);
            
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
    
    // 测试主方法
    public static void main(String[] args) {
        BinaryTree<Integer> tree = new BinaryTree<>();
        
        // 插入节点
        tree.insert(50);
        tree.insert(30);
        tree.insert(70);
        tree.insert(20);
        tree.insert(40);
        tree.insert(60);
        tree.insert(80);
        
        // 打印中序遍历结果
        tree.inorderTraversal();
        
        // 测试查找
        System.out.println("查找30: " + tree.search(30));
        System.out.println("查找100: " + tree.search(100));
        
        // 打印树的高度
        System.out.println("树的高度: " + tree.height());
    }
} 